home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / amiga / convrtrs / pbmplus / update5.lha / src / extra / ppmqvga.c.orig < prev    next >
Encoding:
Text File  |  1993-09-01  |  13.5 KB  |  508 lines
  1. /*
  2.  *  ppmqvga.c - quantize the colors in a pixmap down to a VGA
  3.  *    (256 colors, 6 bits per pixel)
  4.  *
  5.  *  original by Lyle Rains (lrains@netcom.com) as ppmq256 and ppmq256fs
  6.  *  combined, commented, and enhanced by Bill Davidsen (davidsen@crd.ge.com)
  7. */
  8.  
  9. #define DUMPCOLORS 0
  10. #define DUMPERRORS 0
  11.  
  12. #include <stdio.h>
  13. #include <math.h>
  14. #include <malloc.h>
  15. #include "ppm.h"
  16. #ifdef SYSV
  17. #include <string.h>
  18. #define srandom srand
  19. #define random rand
  20. #else /*SYSV*/
  21. #include <strings.h>
  22. #define strchr index
  23. #define strrchr rindex
  24. #endif /*SYSV*/
  25.  
  26. #define min(a,b) ((a) < (b) ? (a) : (b))
  27. #define max(a,b) ((a) > (b) ? (a) : (b))
  28.  
  29. #define RED_BITS   5
  30. #define GREEN_BITS 6
  31. #define BLUE_BITS  5
  32.  
  33. #define MAX_RED    (1 << RED_BITS)
  34. #define MAX_GREEN  (1 << GREEN_BITS)
  35. #define MAX_BLUE   (1 << BLUE_BITS)
  36.  
  37. #define MAXWEIGHT  128
  38. #define STDWEIGHT_DIV  (2 << 8)
  39. #define STDWEIGHT_MUL  (2 << 10)
  40. #define COLORS     256
  41. #define GAIN       4
  42.  
  43. #define BARGRAPH     "__________\b\b\b\b\b\b\b\b\b\b"
  44. #define BARGRAPHLEN  10
  45.  
  46. int color_cube[MAX_RED][MAX_GREEN][MAX_BLUE];
  47.  
  48. unsigned char clut[COLORS][4];
  49. int erropt[COLORS][4];
  50. enum { red, green, blue, count };
  51. int clutx;
  52.  
  53. int weight_convert[MAXWEIGHT];
  54. int total_weight, cum_weight[MAX_GREEN];
  55. int rep_weight, rep_threshold;
  56. int r, g, b, dr, dg, db;
  57. int dither = 0, verbose = 1;
  58.  
  59. pixval maxval;
  60.  
  61. /*
  62. ** 3-D error diffusion dither routine for points in the color cube; used to
  63. ** select the representative colors.
  64. */
  65. diffuse()
  66. {
  67.   int _7_32nds, _3_32nds, _1_16th;
  68.  
  69.   if (clutx < COLORS) {
  70.     if (color_cube[r][g][b] > rep_threshold) {
  71.  
  72.       clut[clutx][red]   = ((2 * r + 1) * (maxval + 1)) / (2 * MAX_RED);
  73.       clut[clutx][green] = ((2 * g + 1) * (maxval + 1)) / (2 * MAX_GREEN);
  74.       clut[clutx][blue]  = ((2 * b + 1) * (maxval + 1)) / (2 * MAX_BLUE);
  75. #if DUMPCOLORS
  76.       if (verbose > 2) {
  77.         /* Dump new color */
  78.         if ((clutx & 3) == 0) {
  79.           fprintf(stderr, "\n  %3d (%2d): ", clutx, rep_threshold);
  80.         }
  81.         fprintf(stderr,
  82.       " (%03d,%03d,%03d)", clut[clutx][red],
  83.       clut[clutx][green], clut[clutx][blue]
  84.     );
  85.       }
  86. #endif
  87.       ++clutx;
  88.       color_cube[r][g][b] -= rep_weight;
  89.     }
  90.     _7_32nds = (7 * color_cube[r][g][b]) / 32;
  91.     _3_32nds = (3 * color_cube[r][g][b]) / 32;
  92.     _1_16th = color_cube[r][g][b] - 3 * (_7_32nds + _3_32nds);
  93.     color_cube[ r  ][ g  ][ b  ]  = 0;
  94.     /* spread error evenly in color space. */
  95.     color_cube[ r  ][ g  ][b+db] += _7_32nds;
  96.     color_cube[ r  ][g+dg][ b  ] += _7_32nds;
  97.     color_cube[r+dr][ g  ][ b  ] += _7_32nds;
  98.     color_cube[ r  ][g+dg][b+db] += _3_32nds;
  99.     color_cube[r+dr][ g  ][b+db] += _3_32nds;
  100.     color_cube[r+dr][g+dg][ b  ] += _3_32nds;
  101.     color_cube[r+dr][g+dg][b+db] += _1_16th;
  102.     /* Conserve the error at edges if possible (which it is, except the last pixel) */
  103.     if (color_cube[r][g][b] != 0) {
  104.       if      (dg != 0)   color_cube[r][g+dg][b] += color_cube[r][g][b];
  105.       else if (dr != 0)   color_cube[r+dr][g][b] += color_cube[r][g][b];
  106.       else if (db != 0)   color_cube[r][g][b+db] += color_cube[r][g][b];
  107.       else fprintf(stderr, "\nlost error term\n");
  108.     }
  109.   }
  110.   color_cube[r][g][b] = -1;
  111. }
  112.  
  113. /*
  114. ** Find representative color nearest to requested color.  Check color cube
  115. ** for a cached color index.  If not cached, compute nearest and cache result.
  116. */
  117. int nearest_color(pP)
  118.   register pixel *pP;
  119. {
  120.   register unsigned char *test;
  121.   register unsigned i;
  122.   unsigned long min_dist_sqd, dist_sqd;
  123.   int nearest;
  124.   int *cache;
  125.   int r, g, b;
  126.  
  127.   r = ((int)(PPM_GETR(*pP)));
  128.   g = ((int)(PPM_GETG(*pP)));
  129.   b = ((int)(PPM_GETB(*pP)));
  130.   if ((i = maxval + 1) == 256) {
  131.     cache = &(color_cube[r>>(8-RED_BITS)][g>>(8-GREEN_BITS)][b>>(8-BLUE_BITS)]);
  132.   }
  133.   else {
  134.     cache = &(color_cube[(r<<RED_BITS)/i][(g<<GREEN_BITS)/i][(b<<BLUE_BITS)/i]);
  135.   }
  136.   if (*cache >= 0) return *cache;
  137.   min_dist_sqd = ~0;
  138.   for (i = 0; i < COLORS; ++i) {
  139.     test = clut[i];
  140.     dist_sqd = 3 * (r - test[red])   * (r - test[red])
  141.              + 4 * (g - test[green]) * (g - test[green])
  142.              + 2 * (b - test[blue])  * (b - test[blue]);
  143.     if (dist_sqd < min_dist_sqd) {
  144.       nearest = i;
  145.       min_dist_sqd = dist_sqd;
  146.     }
  147.   }
  148.   return (*cache = nearest);
  149. }
  150.  
  151.  
  152. /* Errors are carried at FS_SCALE times actual size for accuracy */
  153. #define _7x16ths(x)   ((7 * (x)) / 16)
  154. #define _5x16ths(x)   ((5 * (x)) / 16)
  155. #define _3x16ths(x)   ((3 * (x)) / 16)
  156. #define _1x16th(x)    ((x) / 16)
  157. #define NEXT(line)    (!(line))
  158. #define FS_SCALE      1024
  159.  
  160. typedef int fs_err_array[2][3];
  161.  
  162. void fs_diffuse (fs_err, line, color, err)
  163.   fs_err_array *fs_err;
  164.   int line, color;
  165.   int err;
  166. {
  167.   fs_err[1] [line]       [color] += _7x16ths(err);
  168.   fs_err[-1][NEXT(line)] [color] += _3x16ths(err);
  169.   fs_err[0] [NEXT(line)] [color] += _5x16ths(err);
  170.   fs_err[1] [NEXT(line)] [color]  = _1x16th(err); /* straight assignment */
  171. }
  172.  
  173. main(argc, argv)
  174.   int argc;
  175.   char *argv[];
  176. {
  177.   FILE *ifd;
  178.   pixel **pixels;
  179.   register pixel *pP;
  180.   int rows, cols, row;
  181.   register int col;
  182.   int limitcol;
  183.   int i, j, k;
  184.   char *ccP;
  185.   int *errP;
  186.   unsigned char *clutP;
  187.   int nearest;
  188.   fs_err_array *fs_err_lines, *fs_err;
  189.   int fs_line = 0;
  190.   char *usage = "[ppmfile]";
  191.   char *pm_progname;
  192.   /* getopt stuff */
  193.   extern int optind;
  194.   extern char *optarg;
  195.  
  196.   /* option parsing */
  197.   while ((i = getopt(argc, argv, "dvq")) >= 0) {
  198.     switch (i) {
  199.     case 'd': /* dither */
  200.       dither = 1; break;
  201.     case 'v': /* verbose */
  202.       ++verbose;
  203.       break;
  204.     case 'q': /* quiet */
  205.       verbose = 0; break;
  206.     }
  207.   }
  208.  
  209.   if ((pm_progname = strrchr(argv[0], '/')) != NULL) ++pm_progname;
  210.   else pm_progname = argv[0];
  211.  
  212.   if ((argc - optind) > 1) pm_usage( usage );
  213.  
  214.   if ((argc - optind) == 1) ifd = pm_openr( argv[optind] );
  215.   else ifd = stdin;
  216.  
  217.   /*
  218.   ** Step 0: read in the image.
  219.   */
  220.   pixels = ppm_readppm( ifd, &cols, &rows, &maxval );
  221.   pm_close( ifd );
  222.  
  223.   /*
  224.   ** Step 1: catalog the colors into a color cube.
  225.   */
  226.   if (verbose) {
  227.     fprintf( stderr, "%s: building color tables %s", pm_progname, BARGRAPH);
  228.     j = (i = rows / BARGRAPHLEN) / 2;
  229.   }
  230.  
  231.   /* Count all occurances of each color */
  232.   for (row = 0; row < rows; ++row) {
  233.  
  234.     if (verbose) {
  235.       if (row > j) {
  236.         putc('*', stderr);
  237.         j += i;
  238.       }
  239.     }
  240.  
  241.     if (maxval == 255) {
  242.       for (col = 0, pP = pixels[row]; col < cols; ++col, ++pP) {
  243.         ++(color_cube[PPM_GETR(*pP) / (256 / MAX_RED)]
  244.                      [PPM_GETG(*pP) / (256 / MAX_GREEN)]
  245.                      [PPM_GETB(*pP) / (256 / MAX_BLUE)]
  246.         );
  247.       }
  248.     }
  249.     else {
  250.       for (col = 0, pP = pixels[row]; col < cols; ++col, ++pP) {
  251.         r = (PPM_GETR(*pP) * MAX_RED)  / (maxval + 1);
  252.         g = (PPM_GETG(*pP) * MAX_GREEN)/ (maxval + 1);
  253.         b = (PPM_GETB(*pP) * MAX_BLUE) / (maxval + 1);
  254.         ++(color_cube[r][g][b]);
  255.       }
  256.     }
  257.   }
  258.  
  259.   /*
  260.   ** Step 2: Determine weight of each color and the weight of a representative color.
  261.   */
  262.   /* Initialize logarithmic weighing table */
  263.   for (i = 2; i < MAXWEIGHT; ++i) {
  264.     weight_convert[i] = (int) (100.0 * log((double)(i)));
  265.   }
  266.  
  267.   k = rows * cols;
  268.   if ((k /= STDWEIGHT_DIV) == 0) k = 1;
  269.   total_weight = i = 0;
  270.   for (g = 0; g < MAX_GREEN; ++g) {
  271.     for (r = 0; r < MAX_RED; ++r) {
  272.       for (b = 0; b < MAX_BLUE; ++b) {
  273.         register int weight;
  274.         /* Normalize the weights, independent of picture size. */
  275.         weight = color_cube[r][g][b] * STDWEIGHT_MUL;
  276.         weight /= k;
  277.         if (weight) ++i;
  278.         if (weight >= MAXWEIGHT) weight = MAXWEIGHT - 1;
  279.         total_weight += (color_cube[r][g][b] = weight_convert[weight]);
  280.       }
  281.     }
  282.     cum_weight[g] = total_weight;
  283.   }
  284.   rep_weight = total_weight / COLORS;
  285.  
  286.   if (verbose) {
  287.     putc('\n', stderr);
  288.     if (verbose > 1) {
  289.       fprintf(stderr, "  found %d colors with total weight %d\n",
  290.         i, total_weight);
  291.       fprintf(stderr, "  avg weight for colors used  = %7.2f\n",
  292.         (float)total_weight/i);
  293.       fprintf(stderr, "  avg weight for all colors   = %7.2f\n",
  294.         (float)total_weight/(MAX_RED * MAX_GREEN * MAX_BLUE));
  295.       fprintf(stderr, "  avg weight for final colors = %4d\n", rep_weight);
  296.     }
  297.     fprintf( stderr, "%s: selecting new colors...", pm_progname);
  298.   }
  299.  
  300.   /* Magic foo-foo dust here.  What IS the correct way to select threshold? */
  301.   rep_threshold = total_weight * (28 + 110000/i) / 95000;
  302.  
  303.   /*
  304.   ** Step 3: Do a 3-D error diffusion dither on the data in the color cube
  305.   ** to select the representative colors.  Do the dither back and forth in
  306.   ** such a manner that all the error is conserved (none lost at the edges).
  307.   */
  308. #if !DUMPCOLORS
  309.   if (verbose > 2) {
  310.     fprintf(stderr, "\nrep_threshold: %d", rep_threshold);
  311.   }
  312. #endif
  313.   dg = 1;
  314.   for (g = 0; g < MAX_GREEN; ++g) {
  315.     dr = 1;
  316.     for (r = 0; r < MAX_RED; ++r) {
  317.       db = 1;
  318.       for (b = 0; b < MAX_BLUE - 1; ++b) diffuse();
  319.       db = 0;
  320.       diffuse();
  321.       ++b;
  322.       if (++r == MAX_RED - 1) dr = 0;
  323.       db = -1;
  324.       while (--b > 0) diffuse();
  325.       db = 0;
  326.       diffuse();
  327.     }
  328.     /* Modify threshold to keep rep points proportionally distribited */
  329.     if ((j = clutx - (COLORS * cum_weight[g]) / total_weight) != 0) {
  330.       rep_threshold += j * GAIN;
  331. #if !DUMPCOLORS
  332.       if (verbose > 2) {
  333.         fprintf(stderr, " %d", rep_threshold);
  334.       }
  335. #endif
  336.     }
  337.     if (++g == MAX_GREEN - 1) dg = 0;
  338.     dr = -1;
  339.     while (r-- > 0) {
  340.       db = 1;
  341.       for (b = 0; b < MAX_BLUE - 1; ++b) diffuse();
  342.       db = 0;
  343.       diffuse();
  344.       ++b;
  345.       if (--r == 0) dr = 0;
  346.       db = -1;
  347.       while (--b > 0) diffuse();
  348.       db = 0;
  349.       diffuse();
  350.     }
  351.     /* Modify threshold to keep rep points proportionally distribited */
  352.     if ((j = clutx - (COLORS * cum_weight[g]) / total_weight) != 0) {
  353.       rep_threshold += j * GAIN;
  354. #if !DUMPCOLORS
  355.       if (verbose > 2) {
  356.         fprintf(stderr, " %d", rep_threshold);
  357.       }
  358. #endif
  359.     }
  360.   }
  361.  
  362.   /*
  363.   ** Step 4: check the error associted with the use of each color, and
  364.   ** change the value of the color to minimize the error.
  365.   */
  366.   if (verbose) {
  367.     fprintf( stderr, "\n%s: Reducing errors in the color map %s",
  368.       pm_progname, BARGRAPH);
  369.     j = (i = rows / BARGRAPHLEN) / 2;
  370.   }
  371.   for (row = 0; row < rows; ++row) {
  372.  
  373.     if (verbose) {
  374.       if (row > j) {
  375.         putc('*', stderr);
  376.         j += i;
  377.       }
  378.     }
  379.  
  380.     pP = pixels[row];
  381.     for (col = 0; col < cols; ++col) {
  382.       nearest = nearest_color(pP);
  383.       errP = erropt[nearest]; clutP = clut[nearest];
  384.       errP[red]   += PPM_GETR(*pP) - clutP[red];
  385.       errP[green] += PPM_GETG(*pP) - clutP[green];
  386.       errP[blue]  += PPM_GETB(*pP) - clutP[blue];
  387.       ++errP[count];
  388.       ++pP;
  389.     }
  390.   }
  391. #if DUMPERRORS
  392.     if (verbose) {
  393.       fprintf( stderr, "\n  Color    Red Err  Green Err   Blue Err  Count");
  394.     }
  395. #endif
  396.   for (i = 0; i < COLORS; ++i) {
  397.     clutP = clut[i]; errP = erropt[i];
  398.     j = errP[count];
  399.     if (j > 0) {
  400.       j *= 4;
  401. #if DUMPERRORS
  402.       if (verbose) {
  403.         fprintf( stderr, "\n   %4d %10d %10d %10d %6d",
  404.           i, errP[red]/j, errP[green]/j, errP[blue]/j, j);
  405.       }
  406. #endif
  407.       clutP[red]   += (errP[red]   / j) * 4;
  408.       clutP[green] += (errP[green] / j) * 4;
  409.       clutP[blue]  += (errP[blue]  / j) * 4;
  410.     }
  411.   }
  412.   /* Reset the color cache. */
  413.   for (r = 0; r < MAX_RED; ++r)
  414.     for (g = 0; g < MAX_GREEN; ++g)
  415.       for (b = 0; b < MAX_BLUE; ++b)
  416.         color_cube[r][g][b] = -1;
  417.  
  418.  
  419.   /*
  420.   ** Step 5: map the colors in the image to their closest match in the
  421.   ** new colormap, and write 'em out.
  422.   */
  423.   if (verbose) {
  424.     fprintf( stderr, "\n%s: Mapping image to new colors %s",
  425.       pm_progname, BARGRAPH);
  426.     j = (i = rows / BARGRAPHLEN) / 2;
  427.   }
  428.   ppm_writeppminit( stdout, cols, rows, maxval, 0 );
  429.  
  430.   if (dither) {
  431.     fs_err_lines = (fs_err_array *) calloc((cols + 2), sizeof(fs_err_array));
  432.  
  433.     if (fs_err_lines == NULL) {
  434.       fprintf(stderr, "\n%s: can't allocate Floyd-Steinberg error array.\n",
  435.         pm_progname);
  436.       exit(1);
  437.     }
  438.   }
  439.  
  440.   for (row = 0; row < rows; ++row) {
  441.  
  442.     if (verbose) {
  443.       if (row > j) {
  444.         putc('*', stderr);
  445.         j += i;
  446.       }
  447.     }
  448.  
  449.     if (dither) {
  450.       fs_err = fs_err_lines + 1;
  451.       fs_err[0][NEXT(fs_line)][red]   = 0;
  452.       fs_err[0][NEXT(fs_line)][green] = 0;
  453.       fs_err[0][NEXT(fs_line)][blue]  = 0;
  454.     }
  455.  
  456.     pP = pixels[row];
  457.     for (col = 0; col < cols; ++col) {
  458.  
  459.       if (dither) {
  460.         r = FS_SCALE * (int)(PPM_GETR(*pP)) + fs_err[0][fs_line][red];
  461.         if (r > FS_SCALE * (int)maxval) r = FS_SCALE * (int)maxval;
  462.         if (r < 0) r = 0;
  463.         g = FS_SCALE * (int)(PPM_GETG(*pP)) + fs_err[0][fs_line][green];
  464.         if (g > FS_SCALE * (int)maxval) g = FS_SCALE * (int)maxval;
  465.         if (g < 0) g = 0;
  466.         b = FS_SCALE * (int)(PPM_GETB(*pP)) + fs_err[0][fs_line][blue];
  467.         if (b > FS_SCALE * (int)maxval) b = FS_SCALE * (int)maxval;
  468.         if (b < 0) b = 0;
  469.  
  470.         PPM_ASSIGN(
  471.           *pP, (pixval)(r/FS_SCALE), (pixval)(g/FS_SCALE),
  472.       (pixval)(b/FS_SCALE)
  473.         );
  474.       }
  475.       nearest = nearest_color(pP);
  476.       if (nearest < 0 || nearest > COLORS - 1) {
  477.         fprintf(stderr, "  nearest = %d; out of range\n", nearest);
  478.         exit(1);
  479.       }
  480.       clutP = clut[nearest];
  481.  
  482.       if (dither) {
  483.         r -= FS_SCALE * (int)clutP[red];
  484.         g -= FS_SCALE * (int)clutP[green];
  485.         b -= FS_SCALE * (int)clutP[blue];
  486.  
  487.         fs_diffuse(fs_err, fs_line, red,   r);
  488.         fs_diffuse(fs_err, fs_line, green, g);
  489.         fs_diffuse(fs_err, fs_line, blue,  b);
  490.       }
  491.  
  492.       PPM_ASSIGN( *pP, clutP[red], clutP[green], clutP[blue]);
  493.  
  494.       if (dither) ++fs_err;
  495.       ++pP;
  496.     }
  497.  
  498.     ppm_writeppmrow( stdout, pixels[row], cols, maxval, 0 );
  499.  
  500.     fs_line = NEXT(fs_line);
  501.   }
  502.   if (verbose) {
  503.     fprintf( stderr, "\n%s: done.\n", pm_progname);
  504.   }
  505.  
  506.   exit(0);
  507. }
  508.